//
// Created by DengLibin on 2019/1/8 0008.
//
#include <vector>
#include <iostream>
#include <map>

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };
using namespace std;
class Solution {
public:
    /**
     * 从数组中找出和为指定值的两个数的下标
     * @param nums
     * @param target
     * @return
     */
    vector<int> twoSum1(vector<int>& nums, int target) {
        vector<int> v ;
        for(int i = 0; i < nums.size() -1; i++){
            for(int j = i+1; j < nums.size(); j++ ){
                if(nums[i] + nums[j] == target){
                    v.push_back(i);
                    v.push_back(j);
                }
            }
        }
        return v;
    }
  /**
   * 从数组中找出和为指定值的两个数的下标
   * @param nums
   * @param target
   * @return
   */
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> v ;
        map<int, int> m;
        for(int i = 0; i < nums.size(); i++){
            int key = target - nums[i];
            map<int, int>::iterator it = m.find(key);
            if(it != m.end()){
                v.push_back(it->second);
                v.push_back(i);
                return v;
            }
            m.insert(make_pair(nums[i],i));
        }
        return v;
    }
    /**
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
     * @param l1
     * @param l2
     * @return
     */
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode * tempL1=l1;
        ListNode * tempL2=l2;
        ListNode * headNode = NULL;
        ListNode * tempNode = NULL;
        int tempI = 0;//进位大小
        int sum = 0;
        while(tempL1 != NULL || tempL2 != NULL){
            sum = (tempL1 == NULL ? 0 :tempL1->val) + (tempL2 == NULL ? 0 :tempL2->val) + tempI;
            tempI = sum / 10;
            sum = sum % 10;
            if(headNode == NULL){
                headNode = new ListNode(sum);
                tempNode = headNode;
            } else{
                ListNode * node = new ListNode(sum);
                tempNode->next = node;
                tempNode = node;
            }
            tempL1 = tempL1 == NULL ? NULL : tempL1->next;
            tempL2 = tempL2 == NULL ? NULL : tempL2->next;
        }
        if(tempI != 0){
            ListNode * node = new ListNode(tempI);
            tempNode->next = node;
        }
        return headNode;
    }



};

void test48_1(){
    Solution * solution = new Solution();
    vector<int> v;
    v.push_back(2);
    v.push_back(7);
    v.push_back(11);
    v.push_back(15);
    vector<int> rv = solution->twoSum(v, 9);
    for(vector<int>::iterator it = rv.begin(); it<rv.end(); it++){
        cout << *it<<endl;
    }

    delete solution;
}
void test48_2(){
    ListNode * node1_1 = new ListNode(2);
    ListNode * node1_2 = new ListNode(4);
    ListNode * node1_3 = new ListNode(3);
    node1_1->next = node1_2;
    node1_2->next = node1_3;

    ListNode * node2_1 = new ListNode(5);
    ListNode * node2_2 = new ListNode(6);
    ListNode * node2_3 = new ListNode(6);
    node2_1->next = node2_2;
    node2_2->next = node2_3;

    Solution * solution = new Solution();
    ListNode * node = solution->addTwoNumbers(node1_1, node2_1);
    for(ListNode* tempNode = node; tempNode != NULL; tempNode=tempNode->next){
        cout<<tempNode->val;
    }

}
int main48(){
    test48_2();
    return 0;
}

